﻿#include <gtest/gtest.h>

#include <learn/stl/list.h>
#include <learn/stl/sort.h>
#include <learn/stl/tree.h>

#include <algorithm>
#include <iostream>
#include <random>
#include <set>
#include <vector>

using namespace xi;
using namespace xi::stl;

#define TIMES 100
#define BUF_SIZE 100

TEST(TestTree, bin_tree)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        std::vector<double> arr(BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        Binary_Tree<double, std::greater<double>> rbt;
        for (int i = 0; i < BUF_SIZE; i++)
            rbt.insert(arr[i]);

        std::sort(arr.begin(), arr.end());
        std::reverse(arr.begin(), arr.end());
        while (!arr.empty())
        {
            EXPECT_DOUBLE_EQ(arr.front(), rbt.min()->value);
            EXPECT_DOUBLE_EQ(arr.back(), rbt.max()->value);
            // if (rbt.Size() < 40)
            //     rbt.draw();

            for (int j = 0; j < arr.size(); j++)
            {
                // 注意这里如果有重复元素，index_of 获得的是第一次出现的位置，因此不比较索引而是直接比较值
                EXPECT_DOUBLE_EQ(arr[j], *(rbt.begin() + j));

                auto node = rbt.find(arr[j]);
                EXPECT_DOUBLE_EQ(arr[j], node->value);
            }

            int j = 0;
            for (auto node : rbt)
            {
                EXPECT_DOUBLE_EQ(arr[j], node);
                j++;
            }

            // 随机删除元素
            int d = rand() % arr.size();
            auto it = arr.begin() + d;
            rbt.remove(*it);
            arr.erase(it);
        }
    }
}

TEST(TestTree, rb_tree)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        std::vector<double> arr(BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        RB_Tree<double, std::greater<double>> rbt;
        for (int i = 0; i < BUF_SIZE; i++)
            rbt.insert(arr[i]);

        std::sort(arr.begin(), arr.end());
        std::reverse(arr.begin(), arr.end());
        while (!arr.empty())
        {
            EXPECT_TRUE(rbt.black_height() < (rbt.height() * 2));
            // EXPECT_EQ(arr.size(), rbt.size());
            EXPECT_DOUBLE_EQ(arr.front(), rbt.min()->value);
            EXPECT_DOUBLE_EQ(arr.back(), rbt.max()->value);
            // if (rbt.height() < 4)
            //     rbt.draw();

            for (int j = 0; j < arr.size(); j++)
            {
                auto node = rbt.find(arr[j]);
                EXPECT_DOUBLE_EQ(arr[j], node->value);
            }

            // 随机删除元素
            int d = rand() % arr.size();
            auto it = arr.begin() + d;
            rbt.remove(*it);
            arr.erase(it);
        }
    }
}

TEST(TestTree, interval_tree)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        std::vector<std::tuple<double, double>> arr(BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            double l = u(generator);
            arr[i] = {l, l + u(generator)};
        }

        Interval_Tree<double> rbt;
        for (int i = 0; i < BUF_SIZE; i++)
            rbt.insert(arr[i]);

        std::sort(arr.begin(), arr.end());
        int countFailed = 0;
        while (!arr.empty())
        {
            EXPECT_TRUE(arr.front() == rbt.min()->value);
            EXPECT_TRUE(arr.back() == rbt.max()->value);
            // if (rbt.Size() < 40)
            //     rbt.draw();

            for (int j = 0; j < arr.size(); j++)
            {
                // 注意这里如果有重复元素，index_of 获得的是第一次出现的位置，因此不比较索引而是直接比较值
                EXPECT_TRUE(arr[j] == *(rbt.begin() + j));

                auto node = rbt.find(arr[j]);
                EXPECT_TRUE(arr[j] == node->value);
            }

            int j = 0;
            for (auto node : rbt)
            {
                EXPECT_TRUE(arr[j] == node);
                j++;
            }

            // 随机生成区间，测试 overlap
            double l = u(generator);
            std::tuple<double, double> interval = {l, l + u(generator)};
            bool overlap = false;
            for (int j = 0; j < arr.size(); j++)
            {
                auto value = arr[j];
                if (std::get<0>(interval) < std::get<0>(value) && std::get<1>(interval) > std::get<0>(value))
                {
                    overlap = true;
                    break;
                }
                if (std::get<0>(interval) < std::get<1>(value) && std::get<1>(interval) > std::get<1>(value))
                {
                    overlap = true;
                    break;
                }
                if (std::get<0>(value) < std::get<0>(interval) && std::get<1>(value) > std::get<0>(interval))
                {
                    overlap = true;
                    break;
                }
                if (std::get<0>(value) < std::get<1>(interval) && std::get<1>(value) > std::get<1>(interval))
                {
                    overlap = true;
                    break;
                }
            }

            auto node = rbt.overlap(interval);
            if (node == rbt.nil())
            {
                EXPECT_FALSE(overlap);
            }
            if (node != rbt.nil())
            {
                EXPECT_TRUE(overlap);
            }

            // 随机删除元素
            int d = rand() % arr.size();
            auto it = arr.begin() + d;
            rbt.remove(*it);
            arr.erase(it);
        }
    }
}

TEST(TestTree, mn_tree)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    auto func = [](MN_Tree<double>::Node *node) { std::cout << node->value << " "; };

    int N = TIMES;
    while (N-- > 0)
    {
        std::vector<double> arr(BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        MN_Tree<double> rbt;
        std::vector<MN_Tree<double>::Node *> nodes;
        MN_Tree<double>::Node *root = rbt.insert(arr[0]);
        for (int i = 1; i < BUF_SIZE; i++)
        {
            nodes.push_back(rbt.insert(arr[i], root));
            std::shuffle(nodes.begin(), nodes.end(), generator);
            root = nodes.back();
        }

        std::sort(arr.begin(), arr.end());
        while (!arr.empty())
        {
            for (int j = 0; j < arr.size(); j++)
            {
                auto node = rbt.find(arr[j]);
                EXPECT_DOUBLE_EQ(arr[j], node->value);
            }

            // 随机删除元素
            int d = rand() % arr.size();
            auto it = arr.begin() + d;
            rbt.remove(*it);
            arr.erase(it);
        }
    }
}

TEST(TestList, list)
{
    List<int> list;

    for (int i = 0; i < 10; i++)
    {
        list.push_front(i);
    }

    int i = 0;
    for (auto it = list.begin(); it != list.end(); it++)
    {
        EXPECT_EQ(9 - i, *it);
        i++;
    }

    for (int i = 0; i < 10; i++)
    {
        EXPECT_EQ(9 - i, list.front());
        list.pop_front();
    }
}

TEST(TestList, list_remove)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        List<double> list;
        std::vector<double> arr(BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
            list.push_front(arr[i]);
            EXPECT_EQ(list.size(), i + 1);
        }

        while (!arr.empty())
        {
            int d = rand() % arr.size();
            auto it = arr.begin() + d;
            EXPECT_TRUE(list.find(*it) != list.end());
            list.remove(*it);
            arr.erase(it);
            EXPECT_EQ(list.size(), arr.size());
        }
    }
}

TEST(TestList, list_remove_dup)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_int_distribution<int> u(0, 10);

    int N = TIMES;
    while (N-- > 0)
    {
        List<int> list;
        std::set<int> arr;
        for (int i = 0; i < BUF_SIZE; i++)
        {
            auto val = u(generator);
            arr.insert(val);
            list.push_front(val);
        }

        list.remove_duplicates();
        EXPECT_EQ(list.size(), arr.size());
    }
}

TEST(TestSort, bubble_sort)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        double arr[BUF_SIZE];
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        double dst[BUF_SIZE];
        std::copy(arr, arr + BUF_SIZE, dst);

        bubble_sort(arr, BUF_SIZE);
        std::sort(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }
    }
}

TEST(TestSort, insert_sort)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        double arr[BUF_SIZE];
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        double dst[BUF_SIZE];
        std::copy(arr, arr + BUF_SIZE, dst);

        insert_sort(arr, BUF_SIZE);
        std::sort(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }
    }
}

TEST(TestSort, binary_insert_sort)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        double arr[BUF_SIZE];
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        double dst[BUF_SIZE];
        std::copy(arr, arr + BUF_SIZE, dst);

        binary_insert_sort(arr, BUF_SIZE);
        std::sort(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }
    }
}

TEST(TestSort, shell_sort)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        double arr[BUF_SIZE];
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        double dst[BUF_SIZE];
        std::copy(arr, arr + BUF_SIZE, dst);

        shell_sort(arr, BUF_SIZE);
        std::sort(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }
    }
}

TEST(TestSort, merge_sort)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        double arr[BUF_SIZE];
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        double dst[BUF_SIZE];
        std::copy(arr, arr + BUF_SIZE, dst);

        merge_sort(arr, BUF_SIZE);
        std::sort(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }
    }
}

TEST(TestSort, quick_sort)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        double arr[BUF_SIZE];
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        double dst[BUF_SIZE];
        std::copy(arr, arr + BUF_SIZE, dst);

        quick_sort(arr, BUF_SIZE);
        std::sort(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }
    }
}

TEST(TestSort, heap)
{
    std::mt19937 generator((unsigned int)time(nullptr));
    std::uniform_real_distribution<double> u(0, 1);

    int N = TIMES;
    while (N-- > 0)
    {
        double arr[BUF_SIZE];
        for (int i = 0; i < BUF_SIZE; i++)
        {
            arr[i] = u(generator);
        }

        double dst[BUF_SIZE];
        std::copy(arr, arr + BUF_SIZE, dst);

        make_heap(arr, BUF_SIZE);
        std::make_heap(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }

        heap_sort(arr, BUF_SIZE);
        std::sort_heap(dst, dst + BUF_SIZE);
        for (int i = 0; i < BUF_SIZE; i++)
        {
            EXPECT_DOUBLE_EQ(arr[i], dst[i]);
        }
    }
}